// SGI STL第一级、第二级配置器实现的部分代码
#ifndef __SGI_STL_INTERNAL_ALLOC_H
#define __SGI_STL_INTERNAL_ALLOC_H

#    include <stdio.h>
#    include <stdlib.h>

// 第一级配置器 __malloc_alloc_template
/*
SGI第一级配置器的allocate()和realloc()都是在调用malloc()和realloc()不成功后
改调用oom_malloc()和oom_realloc()它们都有内循环，不断调用“内存不足处理例程”，期望在某次调用之后，获得足够的内存而圆满完成任务。
但如果“内存不足处理例程”并未被客端设定，oom_malloc()和oom_realloc()
便直接调用__THROW_BAD_ALLOC，丢出bad_alloc异常信息，或利用exit(1)中止程序。
*/
template <int inst>
class __malloc_alloc_template
{
private:
// 以下都是函数指针，所代表的函数用以处理内存不足的情况
// oom : out of memory
    static void* oom_malloc(size_t);
    static void* oom_realloc(void *, size_t);
    static void (* __malloc_alloc_oom_handler) ();
public:
    static void * allocate(size_t n)
    {
        void *result = malloc(n); // 第一级配置器直接使用malloc()
        // 以下无法满足需求时，改用oom_malloc()
        if (0 == result)
            result = oom_malloc(n);
        return result;
    }

    static void deallocate(void *p, size_t /* n */)
    {
        free(p); // 第一级配置器直接使用free()
    }

    static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
    {
        void * result = realloc(p, new_sz); // 第一级配置器直接使用realloc()
        if (0 == result)
            result = oom_realloc(p, new_sz);
        return result;
    }

    // 以下仿真C++的set_new_handler() -> 可以通过它指定自己的out-of-memory handler
    static void (* set_malloc_handler(void (*f)()))()
    {
        void (* old) () = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return (old);
    }
};

// 初值为0，有待客端设定
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;

template <int inst>
void *__malloc_alloc_template<inst>::oom_malloc(size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    // 不断尝试释放、配置、再释放、再配置
    for (;;)
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler)
            throw std::bad_alloc();
        (*my_malloc_handler)(); // 调用处理例程，企图释放内存
        result = malloc(n); // 再次尝试配置内存
        if (result)
            return (result);
    }
}

template <int inst>
void *__malloc_alloc_template<inst>::oom_realloc(void * p, size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    // 不断尝试释放、配置、再释放、再配置
    for (;;)
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler)
            throw std::bad_alloc();
        (*my_malloc_handler)(); // 调用处理例程，企图释放内存
        result = realloc(p, n); // 再次尝试配置内存
        if (result)
            return (result);
    }
}

// 直接将参数inst指定为0
typedef __malloc_alloc_template<0> malloc_alloc;


enum { __ALIGN = 8 }; // 小型区块的上调边界
enum { __MAX_BYTES = 128 }; // 小型区块的上限
enum { __NFREELISTS = __MAX_BYTES/__ALIGN }; // free-lists个数

// 第二级配置器 __default_alloc_template
template <bool threads, int inst>
class __default_alloc_template
{
public:
    static void * allocate(size_t n);
    static void deallocate(void *p, size_t n);
    static void * realloca(void *p, size_t old_sz, size_t new_sz);

private:
    // 将bytes上调至8的倍数
    static size_t ROUND_UP(size_t bytes)
    {
        return ((bytes) + __ALIGN - 1) & ~(__ALIGN - 1);
    }
    // 根据区块大小，决定使用第n号free-list n从1算起
    static size_t FREELIST_INDEX(size_t bytes)
    {
        return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
    }
    // 返回一个大小为n的对象，并可能加入大小为n的其它区块到free list
    static void *refill(size_t n);
    // 配置一大块空间，可容纳nobjs个大小为size的区块
    static char *chunk_alloc(size_t size, int &nobjs);

    // free-lists节点构造
    union obj
    {
        union obj * free_list_link;
        char client_data[1];
    };
    // 16个free-lists
    static obj * volatile free_list[__NFREELISTS];

    static char *start_free; // 内存池起始位置，只在chunk_alloc()中变化
    static char *end_free; // 内存池结束位置，只在chunk_alloc()中变化
    static size_t heap_size;
};

template <bool threads, int inst>
void *__default_alloc_template<threads, inst>::allocate(size_t)
{
    obj * volatile * my_free_list;
    obj * result;
    // 大于128 bytes就调用第一级配置器
    if (n > (size_t) __MAX_BYTES)
    {
        return (malloc_alloc::allocate(n));
    }
    // 寻找16个free lists中适当的一个
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if (result == 0)
    {
        // 未找到可用的free list，准备重新填充free list
        void *r = refill(ROUND_UP(n));
        return r;
    }
    // 调整free list
    *my_free_list = result->free_list_link;
    return (result);
}

template <bool threads, int inst>
void __default_alloc_template<threads, inst>::deallocate(void *p, size_t n)
{
    obj *q = (obj *)p;
    obj * volatile * my_free_list;

    // 大于128 bytes就调用第一级配置器
    if (n > (size_t) __MAX_BYTES)
    {
        malloc_alloc::deallocate(p, n);
        return;
    }

    // 寻找对应的free list
    my_free_list = free_list + FREELIST_INDEX(n);
    // 调整free list，回收区块
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}

template <bool threads, int inst>
void *__default_alloc_template<threads, inst>::refill(size_t n)
{
    int nobjs = 20;
    // 调用chunk_alloc() 尝试获取nobjs个区块作为free list的新节点
    char * chunk = chunk_alloc(n, nobjs);
    obj * volatile * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;

    // 如果只获得一个区块，这个区块就分配给调用者用，free list无新节点
    if (1 == nobjs)
        return (chunk);
    
    // 否则准备调整free list， 纳入新节点
    my_free_list = free_list + FREELIST_INDEX(n);

    // 以下在chunk空间内建立free list
    result = (obj *) chunk; // 这一块准备返回给客端
    // 引导free list指向新配置的空间（取自内存池）
    *my_free_list = next_obj = (obj *)(chunk + n);
    // 以下将free list的各节点串接起来
    for (i = 1; ; i++)
    {
        // 从1开始，因为第0各将返回给客端
        current_obj = next_obj;
        next_obj = (obj*)((char *)next_obj + n);
        if (nobjs - 1 == i)
        {
            current_obj -> free_list_link = 0;
            break;
        }
        else
        {
            current_obj -> free_list_link = next_obj;
        }
    }
    return (result);
}

// static data member的定义与初值设定
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = 0;

template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = 0;

template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

#endif